package datastruct.algorithm;

//对一个数组表示的堆进行排序
public class HeapSorter {


    public static void main(String[] args) {

        int[] arr = RandomArray.randomCommon(1,1000,10);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+",");
        }
        System.out.println("\n===========================");
        heapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+",");
        }

    }

    public static void heapSort(int[] nums){
        int last = nums.length-1;
        //heapify,从最后一个分支节点开始向上走
        for (int i = (last-1)/2; i >= 0; i--) {
            adjust(nums,i,last);
        }
        //排序过程:每次 把堆顶和末尾交换, 然后 缩短堆范围 并从 堆顶向下调整
        for (int i = last; i > 0; i--) {
            swap(nums,0,i);
            adjust(nums,0,i-1);
        }
    }

    /**
     * 从索引为cur的节点向下调整,调整范围为[cur,last]
     * @param nums
     * @param cur
     * @param last
     */
    public static void adjust(int[] nums, int cur, int last){

        int maxChild = 2*cur+1;
        while (maxChild<=last){
            if(maxChild<last&&nums[maxChild]<nums[maxChild+1]){
                maxChild++; //右子节点较大
            }
            //如果cur小于子节点,交换cur和maxChild的值
            if(nums[cur]<nums[maxChild]) swap(nums,maxChild,cur);
            //1.heapify时是从下往上走,当前节点的子节点都是堆了
            //2.排序时重新调整只需要调整堆顶,其他节点都满足堆
            //所以遇到当前节点大于左右子节点时,返回即可
            else return;
            //从maxChild节点开始往下调整
            cur = maxChild;
            maxChild = 2*cur+1;
        }
    }

    public static void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

